技术与标准丨不经意关键词检索技术综述

作者简介

 韩宗达 

北京邮电大学计算机学院（国家示范性软件学院）网络与交换技术国家重点实验室博士研究生，主要从事隐私保护的协同计算、安全多方计算、差分隐私等方面的研究工作。

 邓宇涛 

北京邮电大学计算机学院（国家示范性软件学院）网络与交换技术国家重点实验室硕士研究生，主要从事隐私保护集合求交、隐私信息检索等方面的研究工作。

 程祥

北京邮电大学计算机学院（国家示范性软件学院）网络与交换技术国家重点实验室教授，博士生导师，主要从事数据隐私保护、数据挖掘等方面的研究工作。

论文引用格式：

韩宗达, 邓宇涛, 程祥. 不经意关键词检索技术综述[J]. 信息通信技术与政策, 2022,48(5):82-90.

不经意关键词检索技术综述

韩宗达  邓宇涛  程祥

（北京邮电大学计算机学院（国家示范性软件学院）网络与交换技术国家重点实验室，北京 100876）

摘要：随着数据成为新型生产要素，数据流通的需求日益增长。但是，数据中存在的隐私信息会在流通过程中面临泄露风险。隐私计算可以在满足隐私保护约束的同时促进数据价值的释放，而不经意关键词检索是隐私计算的基础任务，对隐私计算的落地应用至关重要。对不经意关键词检索的任务定义以及相关任务进行了介绍，详细解析了目前不经意关键词检索的典型技术路线，最后对不经意关键词检索面临的技术挑战以及未来发展趋势进行了分析与探讨。

关键词：不经意关键词检索；信息检索；隐私计算

中图分类号：TP309.7              文献标志码：A

引用格式：韩宗达, 邓宇涛, 程祥. 不经意关键词检索技术综述[J]. 信息通信技术与政策, 2022,48(5):82-90.

DOI：10.12267/j.issn.2096-5931.2022.05.011

0  引言

在信息技术高速发展的数字经济时代，数据的有效利用对推动经济发展、改善社会生活有着重大意义。中共中央、国务院《关于构建更加完善的要素市场化配置体制机制的意见》明确指出数据将与土地、劳动力、资本、技术等传统要素并列，成为一种新的生产要素。然而，数据中隐私信息的存在阻碍了数据价值的充分释放。如何在满足数据隐私保护约束的同时，有效促进数据流通，成为当今时代的关键问题。

隐私计算是解决数据流通与隐私保护之间矛盾的主要手段，其允许多方在隐藏各自敏感信息的前提下执行协同计算，实现“数据可用不可见”。不经意关键词检索（Oblivious Keyword Search，OKS）是在隐私保护下实现信息检索的重要手段，也是隐私计算的基础任务之一。该任务是隐私保护协同计算的关键步骤，为数据处理全流程的隐私保护提供了重要保障。本文对不经意关键词检索的任务定义及其相关任务进行了介绍；然后，结合对现有研究的调研，总结出三种不经意关键词检索的典型技术路线，并分析了各个技术路线的优劣势；最后，对当前不经意关键词检索所面临的主要技术挑战和未来发展趋势进行了分析与探讨。

1  不经意关键词检索

关键词检索是信息检索中的一项基本任务。在传统的关键词检索任务中，数据库端持有一组键值对,用户端通过关键词对数据库发起检索请求，数据库端在接收到查询请求后，通过查询请求中的关键词对持有数据进行检索，并将检索结果反馈给用户端。

然而，传统的关键词检索需要向数据库暴露查询目标的关键词。在实际应用中，查询目标的暴露可能导致隐私信息的泄露，从而使用户利益受到损失。对此，最早由Ogata与Kurosawa^[1]在2002年正式提出了不经意关键词检索的定义与协议。该任务的场景设置包含一个数据库端和用户端，数据库端持有一个存储键值对的数据库D={(x₁,v₁),(x₂,v₂ ),…,(x_n,v_n)}，用户端通过关键词x_i对数据库进行查询，得到对应的值v_i。不经意关键词检索要求同时保护数据库端与用户端的隐私，即数据库端不能得到用户端的查询目标，而用户端不能得到除了查询目标对应值以外的其他信息。

2  相关任务及其关系

2.1  相关任务

隐私信息检索（Private Information Retrieval，PIR）是一种密码学原语，允许用户端对数据库进行查询而不会向数据库暴露任何有关查询目标的信息。具体来说，数据库端持有一个数据库D={D₁,D₂,…,D_n}，数据库中有n个元素，接收者持有一个查询索引i，协议执行完成后，接收者可以得到查询结果D_i。在这个过程中，协议保证接收者不会得到查询索引i的任何相关信息。Chor等^[13]首次提出PIR协议，并随后出现了大量的相关研究工作^[14-26]。现有研究大多基于同态加密^[14-21]，核心思想是构造密文二值向量w∈{0,1}n，若查询索引存在，则向量中对应位置的值为1，反之为0。该技术路线的通信复杂度可以达到对数复杂度，但是其计算代价较高^[16,17,21]。对此，有一部分研究通过编码理论对PIR协议的计算开销与通信开销进行优化^[22-26]，避免使用大量的密码学原语。

不经意传输（Oblivious Transfer，OT）是安全多方计算的基础原语，广泛应用于安全多方计算中，如生成乘法三元组^[47]、构造混淆电路^[48]等。OT允许一方从另一方的n个数据中，获取其中的k个数据。在该过程中，持有数据的一方不应知道另一方的查询目标，而拿到查询结果的一方不应得到除了查询结果以外的信息。传统的OT协议基于公钥密码学构造，如RSA^[45]。为了降低OT的计算开销，一方面研究者们相继提出OT扩展（Oblivious Transfer Extension，OTE）^[40-42]以及SimplestOT^[43,44]，通过降低公钥密码学原语的使用次数，大大提高协议的计算效率；另一方面研究者们提出Random OT^[46]，将大量计算与通信转移到线下进行，提高线上的计算与通信效率。

隐私集合求交（Private Set Intersection，PSI）的场景设置为：持有各自数据集合X、Y的两方期望计算得到双方数据的交集X∩Y，同时不暴露交集以外的其他信息。隐私集合求交具有很长的发展历史，最早被提出用于解决两个公司间寻找共同顾客的问题，目前广泛应用于密码泄露的发现、隐私信息的数据对齐等场景。隐私集合交的现有研究按照技术路线可以划分为基于公钥密码学的PSI^[27-30]、基于电路的PSI^[31,32]、基于OTE的PSI^[12,33-39]以及基于全同态加密的PSI^[4]。基于公钥密码学的PSI通过Diffie-Hellmann、RSA等公钥密码原语构造OPRF协议，并在密文下完成集合求交。基于OTE的PSI通过OTE构造OPRF协议，其计算开销远远小于基于公钥密码学的PSI。两者的共同缺陷在于协议执行的通信复杂度与集合较大一方的集合大小呈线性复杂度关系，不适合于非平衡场景，即双方的集合大小不相等的场景。针对该问题，基于全同态的PSI将协议的通信复杂度降低为与集合较大一方的集合大小呈对数复杂度关系，显著降低了通信开销。但是，基于全同态的PSI在执行时会产生较大的计算开销，使其难以应用于大规模数据场景。

2.2  不经意关键词检索与相关任务的关系

2.2.1  不经意关键词检索、隐私信息检索及不经意传输

不经意关键词检索、隐私信息检索及不经意传输在任务场景上非常类似，均为用户端向持有数据的数据库端发起查询请求，以获取指定数据。三个任务的区别在于查询媒介以及隐私保护要求（见表1）。对于隐私保护要求，PIR仅保护用户端的隐私，即数据库端在协议执行过程中不会得到查询目标的相关信息，OT与OKS会兼顾数据库端的隐私，即用户端仅能得到查询目标对应的值，而无法得到其他位置的值。对于查询媒介，PIR与OT将数组下标作为查询请求，而OKS则使用关键词。因此，PIR和OT存在一个前置条件，用户端在查询前已得知查询目标在数据库中的精确位置。

表1  不经意关键词检索、隐私信息检索以及不经意传输的关系

2.2.2  不经意关键词检索与隐私集合求交不经意关键词检索技术与隐私集合求交存在诸多共同之处，不经意关键词检索可以视作一种特殊的携带标签的非平衡隐私集合求交。携带标签指为隐私集合求交中的数据集合元素添加相应的标签，元素与标签的组合即可视作不经意关键词检索中的键值对。在执行不经意关键词检索协议的过程中，隐私集合求交会隐式进行。因此，部分隐私集合求交协议^[4-6]也成为了现有不经意关键词检索协议的基础。
3  典型技术路线
3.1  基于不经意多项式评估的技术路线不经意多项式评估（Oblivious Polynomial Evaluation，OPE）是一种两方安全计算协议，最早由Naor与Pinkas^[2]于1999年提出。OPE的场景设置中存在一个发送者以及接收者，发送者持有多项式P，接收者持有待评估的输入x，协议执行完成后，接受者获得评估结果P(x)。OPE的安全要求是发送者不能得到输入x的相关信息，接收者除了得到最终结果P(x)，不能得到其他更多关于多项式P的信息。
基于OPE的不经意关键词检索协议最早由Freedman等^[3]在2005年提出，其协议流程如图1所示。协议的核心思想是将数据库中的键值对通过多项式插值法转化为阶数为n-1的多项式P，即n个系数(α₀,α₁,…,α_(n-1))，其中n为键值对的总数，然后双方对多项式进行不经意评估，从而完成关键词检索。OPE的实现基于半同态加密算法，比如Paillier。接收者生成半同态加密的公私钥对(p_k,s_k)，对查询关键词w的0次方至n-1次方依次加密，并将密文发送给发送者。发送者在密文下计算P(w)=∑(i=0)(n-1)α_i w_i，得到密文状态下的多项式评估结果P(w)，并发送给接受者。接收者使用私钥sk解密后即可得到所需的查询结果P(w)。该协议的缺陷在于计算复杂度与通信复杂度均为O(n)，使协议无法支持面向大规模数据的检索任务。Chen等^[4]于2017年提出了基于全同态加密的不经意关键词检索协议Labeled PSI，并于后续的研究工作^[5-6]中对该协议增加了更多的优化措施。Labeled PSI的核心技术路线仍与Freedman等的研究工作保持一致，区别在于利用全同态加密Seal^[8-9]实现OPE。相较于半同态加密，全同态加密可以实现密文间的乘法，并且具备良好的计算并行性质。因此，协议利用全同态加密的相关特点，并结合布谷鸟哈希等一系列技术对协议的通信开销进行了优化，使协议整体的通信复杂度降低为O(logn)。

图1  基于OPE的不经意关键词检索协议流程^[3]

3.2  基于不经意伪随机函数的技术路线不经意伪随机函数（Oblivious Pseudo Random Function，OPRF）是一种以伪随机函数加密为基础的两方安全计算协议。OPRF的场景设置中存在一个发送者以及接收者，发送者持有伪随机函数f的种子k，接收者持有输入x。经过OPRF协议之后，接收者得到得到伪随机函数的计算结果f(x,k)。在协议执行过程中，要求发送者不获得有关x的任何信息，接收者也不会获得有关k的任何信息。
基于OPRF的不经意关键词检索协议的核心思想是双方通过OPRF对关键词完成加密，并保证相同的关键词可以得到相同的密文，然后发送者利用密文关键词构造新的密文键值对，并将其发送给接收者，接收者通过密文键值进行匹配与解密，从而完成信息检索。Freedman^[3]在2005年提出了一种基于宽松OPRF的不经意关键词检索协议。由于严格的OPRF要求接收者不能获取有关发送者密钥的任何信息，Freedman认为达到该安全强度需要付出过高的代价，从而放松了安全要求，使接收者允许获得发送者的部分子密钥。该协议的OPRF执行过程如下：发送者拥有存放键值对的数据库x，首先发送者生成一个由两组随机数作为密钥种子的伪随机函数，然后其将关键词xi∈X切分为两个份额x_i=(x₁,x₂)，并将切分后的两个份额作为索引分别在两个密钥集合r₁,r₂中选取对应的密钥r₁,x₁,r₂,x₂，最后利用选择得到的密钥对关键词x进行加密，得到fr₁,x₁(x_i),fr₂,x₂(x_i)，再将两份关键字密文的异或结果作为关键词x_i的加密结果f_r(x_i)；发送者使用关键词的密文对键值对中的值进行加密,得到新的密文键值对X′；接收者在发起查询请求时对查询关键词w进行切分（w₁，w₂），通过不经意传输^[7]获取发送者密钥集合中特定的两个子密钥r₁,w₁,r₂,w₂，并使用与发送者一致的加密方法对查询请求w进行加密，得到fr(w)。在双方完成OPRF后，接收者得到的关键词密文仅能解密该关键词所对应的密文键值对，在实现信息检索的同时不会对接收者暴露除查询目标以外更多的信息。基于OPRF的不经意关键词检索协议的整体执行流程如图2所示。

图2  基于OPRF的不经意关键词检索协议流程^[3]

3.3  基于Key-ValueStore的技术路线Key-Value Store是一类可以存储键值对的数据结构，包括布谷鸟哈希表^[10]、混淆布隆过滤器^[11]等，本质是一个一维数组。基于Key-Value Store的不经意关键词检索的核心思想是将所有键值对插入到Key-Value Store中，完成关键词到数组下标的映射，从而将不经意关键词检索问题转化为隐私保护的信息检索问题。一般而言，会针对关键词和值构造两个Key-Value Store结构，其中一个结构K用于验证关键词在数组中的具体位置，这是由于关键词w会被映射为k个下标(i₁,…,i_k)，而接收者在协议执行前无法得知关键词在数组中的具体位置；另一个结构V用于存储关键词对应的值，以用于检索操作。在执行PIR的过程中，需要注意三个关键点：接收者必须使用SPIR技术。这是由于PIR无法保证发送者的隐私安全，可能造成非查询关键词的相关信息的泄露；接收者首先通过k个下标(i1,…,ik)执行k次SPIR，以得到所有位置存储的关键词K[i₁],…,K[i_k]，但是其暴露了非查询关键词的位置，使接收者获得了额外信息。因此，为了避免上述信息的泄露，需要引入OPRF技术，双方同时对持有的关键词进行加密。接收者可以通过比较密文确定查询关键词在数组中的位置j，但是其无法通过密文反推出其余关键词的位置。最后，接收者通过SPIR查询数组V中第j个位置的值，获得查询结果V[j]。协议整体执行流程如图3所示。

图3  基于Key-Value Store的不经意关键词检索协议执行流程^[10-11]

3.4  技术路线比较基于OPE的不经意关键词检索协议在通信复杂度上已达到O(logn)，适用于通信资源较贫乏的场景。但是，其代价是计算开销的增长。虽然，Chen等^[5-6]利用SIMD、分箱等手段降低计算开销，但总体上仍较高。因此，当面临大规模数据时，计算开销的过大会限制该技术路线的实际应用。
基于OPRF的不经意关键词检索协议虽然在通信复杂度上为O(n)，但随着OPRF技术的发展，其计算开销逐步降低。Chase等^[12]提出了一种轻量级的OPRF协议，其启发于OT扩展，使用少量的非对称加密生成大量的对称加密密钥，并利用对称加密密钥完成OPRF，降低了公钥密码系统的使用次数，显著提高了协议整体的计算开销。因此，该技术路线适用于计算资源较为贫乏的场景，但缺陷在于需要承担庞大的通信开销，当查询较为频繁时，信道压力会过大。
基于Key-Value Store的不经意关键词检索协议在计算开销与通信开销上取得了较好的平衡。与基于OPE的技术路线相比较，该技术路线的通信复杂度与其一致，均为O(logn)；在计算开销上，虽然仍为线性复杂度，但是该技术路线无需花费较大的计算资源代价生成插值多项式，因此在计算开销上优于基于OPE的技术路线。而与基于OPRF的技术路线相比较，该技术路线虽然具备较小的通信开销，但其所花费的计算开销仍较高。
4  不经意关键词检索技术面临的挑战与发展趋势
不经意关键词检索任务是隐私计算的基础性任务之一。近年来，随着隐私计算的发展，学术界与业界均对不经意关键词检索逐渐引起重视。但是，该任务目前还存在许多挑战亟待解决。本文总结了4个不经意关键词检索任务面临的挑战及发展趋势。
4.1  实时检索协议目前，已有的研究工作均集中于大批量检索的场景，用户端一次性查询多个关键词的值。但是，在实时检索的场景下，查询请求往往是小批量的，甚至是单目标检索。而此时，现有工作的大部分优化措施将失效，导致协议的计算、通信资源代价过高，无法满足实时检索要求。因此，如何构造效率较高的实时检索协议是亟待解决的关键问题。
4.2  适应数据库动态变化的检索协议在实际应用场景中，数据库会实时更新键值对，比如增加新的键值对。而已有工作尚未考虑该场景设置，导致在多次检索中，旧键值对会重复检索，增加了不必要的计算开销与通信开销。因此，在数据库动态变化的场景设置下，如何形成增量式动态检索是一个亟待解决的关键问题。
4.3  多条件检索协议现有的研究工作均聚焦于仅依赖关键词的检索方法，但在实际应用中，用户端可能希望采用多个属性进行组合检索，以拓展协议的筛选能力。例如，信托机构需要向银行检索一批用户的信用评分，但对用户存款设置下限，若低于下限，则无需返回信用评分。在该场景设置下，信托机构不仅需要使用用户的身份证进行筛选，还需要同时考虑该用户的存款是否低于已设置的下限。因此，如何在检索时同时考虑多个查询条件，是一个亟待解决的关键问题。
4.4  隐藏检索结果的后处理技术不经意关键词检索经常会作为数据处理的前置任务，如计算一批用户的平均信用评分前需要通过关键词（比如身份证）取出对应用户的信用评分。从“数据可用不可见”的角度考虑，被检索方可能只希望暴露数据处理结果，而检索结果可以对用户端隐藏。因此，如何在隐藏检索结果的前提下，对检索结果进行后处理是一个亟待解决的关键问题。
5  结束语
随着国家针对个人隐私保护颁布了包括《中华人民共和国网络安全法》《中华人民共和国数据安全法》《中华人民共和国个人信息保护法》《网络数据安全管理条例》等在内的多个法律法规，隐私计算逐渐引起重视并广泛应用于各种应用场景，包括数据联合分析、机器学习联合建模等。不经意关键词检索作为隐私计算的基础性任务之一，对隐私计算的实际部署及应用有着至关重要的作用。相较于隐私信息检索、不经意传输等面向数组下标的检索方法而言，面向关键词的不经意关键词检索任务更贴近于实际应用场景。因此，研究高效的不经意关键词检索协议有助于促进隐私计算的发展，拓展隐私计算的应用边界。
本文通过对现有研究工作进行调研、分析与讨论，将典型技术路线划分为基于OTE的技术路线、基于OPRF的技术路线以及基于Key-Value Store的技术路线。三种技术路线均存在各自的优势与劣势，并且适用于不同的应用场景，而如何取得计算开销与通信开销的最佳平衡，使不经意关键词检索协议的应用场景不再受限，仍需要研究者们的不断探索。进一步地，本文还对现有研究尚未解决的技术挑战进行了分析与探讨，并给出了未来发展趋势：实时检索协议、适应数据库动态变化的检索协议、多条件检索协议以及隐藏检索结果的后处理技术。当不经意关键词检索任务的效率不断提升、功能逐渐完备时，必将在隐私计算的发展潮流中充当更为重要的角色，释放更为巨大的价值。
参考文献
[1] OGATA W, KUROSAWA K. Obliviouskeyword search[J]. Journal of Complexity, 2002,20(2-3):356-371.[2] NAOR M, PINKAS B. Oblivioustransfer with adaptive queries[C]//International Cryptology Conference.Springer Berlin Heidelberg, 1999.[3] FREEDMAN M J, ISHAI Y, PINKAS B, et al. Keywordsearch and oblivious pseudorandom functions[C]//Second International Conference on Theory of Cryptography. Springer Berlin Heidelberg, 2005.[4] CHEN H, LAINE K, RINDAL P. Fastprivate set intersection from homomorphic encryption[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas Texas USA: ACM, 2017.[5] CHEN H, HUANG Z, LAINE K, et al. Labeled PSI fromfully homomorphic encryption with malicious security[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. Toronto Canada: ACM, 2018.[6] CONG K, MORENO R C, GAMA M B, et al. Labeled PSI fromhomomorphic encryption with reduced computation and communication[C]//Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, 2021.[7] NAOR M, REINGOLD O. Number-theoretic constructions of efficient pseudo-random functions[C]//Foundations of Computer Science, 1997. Proceedings. 38th Annual Symposium on, 1997.[8] CHEON J H, KIM A, KIM M, et al. Homomorphic encryption for arithmetic of approximate numbers[C] //International Conference on the Theory and Application of Cryptology and InformationSecurity. Springer, Cham, 2017:409-437.[9] FAN J, VERCAUTEREN F. Somewhat practical fully homomorphic encryption[J]. Cryptology ePrint Archive, 2012.[10] ALI A, LEPOINT T, PATEL S, et al. {CommunicationComputation} trade-offs in {PIR}[C]//30th USENIX Security Symposium(USENIX Security 21), 2021:1811-1828.[11] LEPOINT T, PATEL S, RAYKOVA M, et al. Private join and compute from PIR with default[C]//International Conference on the Theory and Application of Cryptology and InformationSecurity. Springer, Cham, 2021:605-634.[12] CHASE M, MIAO P. Private set intersection in the internet setting from lightweight oblivious PRF[C]//Annual International Cryptology Conference. Springer, Cham, 2020:34-63.[13] CHOR B, GOLDREICH O, Kushilevitz E, et al. Private information retrieval[C]//Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE, 1995:41-50.[14] KUSHILEVITZ E, OSTROVSKY R. Replication is not needed: single database, computationally-private information retrieval[C]//Proceedings 38th annual symposium on foundations of computer science. IEEE, 1997:364-373.[15] STERN J P. A new and efficient all-or-nothing disclosure of secrets protocol[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 1998:357-371.[16] ALI A, LEPOINT T, PATEL S, et al. Communicationcomputation trade-offs in PIR[J]. IACR Cryptol. ePrint Arch, 2019:1483.[17] ANGEL S, CHEN H, LAINE K, et al. PIR with compressed queries and amortized query processing[C]//2018 IEEE Symposium on Security and Privacy(SP). IEEE, 2018:962-979.[18] YI X, KAOSAR M G, PAULET R, et al. Singledatabase private information retrieval from fully homomorphic encryption[J]. IEEE Transactions on Knowledge and Data Engineering, 2012,25(5):1125-1134.[19] MELCHOR C A, BARRIER J, FOUSSE L, et al.XPIR: Private information retrieval for everyone[J]. Proceedings on Privacy Enhancing Technologies, 2016:155-174.[20] ANGEL S, SETTY S. Unobservable communication over fully untrusted infrastructure[C]//12th {USENIX}Symposium on Operating Systems Design and Implementation ({OSDI} 16), 2016:551-569.[21] PARK J, TIBOUCHI M. SHECS-PIR: Somewhat Homomorphic Encryption-Based Compact and Scalable Private Information Retrieval[C]//European Symposium on Research in ComputerSecurity. Springer, Cham, 2020:86-106.[22] CANETTI R, HOLMGREN J, RICHELSON S. Towards doubly efficient private information retrieval[C]//Theory of Cryptography Conference. Springer, Cham, 2017:694-726.[23] HOLZBAUR L, HOLLANTI C, WACHTER-ZEH A. Computationalcode-based single-server private information retrieval[C]//2020 IEEE International Symposium on Information Theory (ISIT). IEEE, 2020:1065-1070.[24] MELCHOR C A , GABORIT P . A lattice-based computationally-efficient private information retrieval protocol[Z], 2007.[25] GROTH J, KIAYIAS A, LIPMAA H. Multi-query computationally-private information retrieval with constant communication rate[C]//International Workshop on Public Key Cryptography. Springer, Berlin,Heidelberg, 2010:107-123.[26] ALFARANO G N, KHATHURIA K, WEGER V. On single server private information retrieval in a coding theory perspective[J]. arXiv preprint arXiv:2008.06417, 2020.[27] FREEDMAN M J, NISSIM K, PINKAS B. Efficient private matching and set intersection[C]//International conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2004:1-19.[28] MEADOWS C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//1986 IEEE Symposium on Security and Privacy. IEEE, 1986:134-134.[29] CRISTOFARO E, TSUDIK G. Practical private set intersection protocols with linear complexity[C]//International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2010:143-159.[30] FREEDMAN M J, HAZAY C, NISSIM K, et al. Efficient set intersection with simulation-based security [J]. Journal of Cryptology, 2016,29(1):115-155.[31] HUANG Y, EVANS D, KATZ J. Private set intersection: are garbled circuits better than custom protocols?[C]//NDSS, 2012.[32] RINDAL P, ROSULEK M. Fastermalicious 2-party secure computation with {online/offline} dual execution[C]//25th USENIX Security Symposium (USENIX Security 16), 2016:297-314.[33] DONG C, CHEN L, WEN Z. When private set intersection meets big data: an efficient and scalable protocol[C]//Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 2013:789-800.[34] RINDAL P, ROSULEK M. Faster malicious 2-party secure computation with online/offline dual execution[C]//25th {USENIX} Security Symposium ({USENIX} Security 16), 2016:297-314.[35] RINDAL P, ROSULEK M. Improved private set intersection against malicious adversaries[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2017: 235-259.[36] RINDAL P, ROSULEK M. Malicious-secure private set intersection via dual execution[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017:1229-1242.[37] KOLESNIKOV V, KUMARESAN R, ROSULEK M, et al. Efficient batched oblivious PRF with applications to private setintersection[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016:818-829.[38] PINKAS B, SCHNEIDER T, ZOHNER M. Faster private set intersection based on {OT} extension[C]//23rd {USENIX} Security Symposium ({USENIX} Security 14), 2014:797-812.[39] CHASE M, MIAO P. Private set intersection in the internet setting from lightweight oblivious PRF[C]//Annual International Cryptology Conference. Springer, Cham, 2020:34-63.[40] ISHAI Y, KILIAN J, NISSIM K, et al. Extending oblivious transfers efficiently[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2003:145-161.[41] KOLESNIKOV V, KUMARESAN R. Improved OT extension for transferring short secrets[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2013:54-70.[42] ASHAROV G, LINDELL Y, SCHNEIDER T, et al. More efficient oblivious transfer and extensions for faster secure computation[C]//Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, 2013:535-548.[43] CHOU T, ORLANDI C. The simplest protocol for oblivious transfer[C]//International Conference on Cryptology and Information Security in Latin America. Springer, Cham, 2015:40-58.[44] HAUCK E, LOSS J. Efficient anduniversally composable protocols for oblivious transfer from the CDH assumption[J]. IACR Cryptol. ePrint Arch, 2017:1011.[45] PEIKERT C, VAIKUNTANATHAN V, WATERS B. A framework for efficient and composable oblivious transfer[C]//Annual international cryptology conference. Springer, Berlin, Heidelberg, 2008:554-571.[46] CLAUDE C. Equivalence between two flavours of oblivious transfers[C]//In A Conference on the Theory and Appli- cations of Cryptographic Techniques on Advances in Cryptol- ogy, CRYPTO’87, 1988.[47] MOHASSEL P, ZHANG Y. Secureml: a system for scalable privacy-preserving machine learning[C]//2017 IEEE symposium on security and privacy(SP). IEEE, 2017:19-38.[48] HUANG Y, EVANS D, KATZ J, et al. Fastersecure {two-party} computation using garbled circuits[C]//20th USENIX Security Symposium (USENIX Security 11), 2011.
A survey on oblivious keyword search
HAN Zongda, DENG Yutao, CHENG Xiang
(State Key Laboratory of Networking and Switching Technology, School of Computer Science (National Pilot Software Engineering School), Beijing University of Posts and Telecommunications, Beijing 100876, China)
Abstract: As data becomes a new factor of production, the demand for data circulation is growing. However, the sensitive information faces the risk of leakage during the circulation process. Privacy-preserving computing can promote the release of data value while satisfying privacy-preserving constraints. Oblivious keyword search (OKS) is one of the basic tasks of privacy-preserving computing, and it is very important for the application of privacy-preserving computing. In this paper, we first introduce the task definition of OKS and the related tasks. Then, we introduce in detail the typical technical routes of OKS. Finally, we analyze and discuss the technical challenges and future research directions of current OKS technology.Keywords: oblivious keyword search; information retrieval; privacy preserving computing

本文刊于《信息通信技术与政策》2022年 第5期

主办：中国信息通信研究院

《信息通信技术与政策》是工业和信息化部主管、中国信息通信研究院主办的专业学术期刊。本刊定位于“信息通信技术前沿的风向标，信息社会政策探究的思想库”，聚焦信息通信领域技术趋势、公共政策、 国家/产业/企业战略，发布前沿研究成果、焦点问题分析、热点政策解读等，推动5G、工业互联网、数字经济、人工智能、区块链、大数据、云计算等技术产业的创新与发展，引导国家技术战略选择与产业政策制定，搭建产、学、研、用的高端学术交流平台。

《信息通信技术与政策》官网开通啦！

为进一步提高期刊信息化建设水平，为广大学者提供更优质的服务，我刊于2020年11月18日起正式推出官方网站，现已进入网站试运行阶段。我们将以更专业的态度、更丰富的内容、更权威的报道，继续提供有前瞻性、指导性、实用性的优秀文稿，为建设网络强国和制造强国作出更大贡献！

《信息通信技术与政策》投稿指南！

   推荐阅读  

你“在看”我吗？